#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int climbStairs(int n) {
        this->memo = vector<int>(n + 1, -1);
        return calSteps(n);
    }
private:
    int calSteps(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        if (this->memo[n] == -1) {
            this->memo[n] = calSteps(n - 1) + calSteps(n - 2);
        }

        return memo[n];
    }
    vector<int> memo;
};

int main(int argc, char *argv[])
{
    Solution s;
    
    int num = s.climbStairs(2);
    cout << num << endl;
    return 0;
}
